package cn.edu.xjtu.work.middleNode;

import cn.edu.xjtu.Util.ListNode.ListNode;

/**
 * 876. 链表的中间结点
 * 
 * 
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * 
 * 如果有两个中间结点，则返回第二个中间结点。
 */
public class Solution {
    /**
     * 快慢指针,快指针每次走两步,慢指针每次走一步
     * 
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 遍历一遍得到长度,第二次遍历直接输出
     * 
     * @param head
     * @return
     */
    public ListNode middleNode1(ListNode head) {
        int len = 0;
        ListNode temp = head;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        int i = 0;
        temp = head;
        while (temp != null) {
            i++;
            if (i == len / 2 + 1) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}
